package cn.yza.算法.Leetcode;

/** 累加数 是一个字符串，组成它的数字可以形成累加序列。

 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

 说明：累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/additive-number
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    一个有效的累加序列至少包含 3 个数；
    除了前两个数以外，其余数等于前面两数之和；
    不会出现前导 0，但是，0 可以单独做为一个数来使用，比如 "101"，
    可以拆分成 1 + 0 = 1，所以，它是累加数。


 * @author Honglixi
 * @create 2022-01-10 16:51
 */
public class Leetcode306 {
    public boolean isAdditiveNumber(String num) {
        return dfs(num, 0, 0, 0, 0);
    }

    /**
     *
     * @param num 传入的数字字符串
     * @param index
     * @param count
     * @param prevprev
     * @param prev
     * @return
     */
    private boolean dfs(String num, int index, int count, long prevprev, long prev) {
        if (index >= num.length()) {
            return count > 2;
        }
        long current = 0;
        for (int i = index; i < num.length(); i++) {
            char c = num.charAt(i);
            if (num.charAt(index) == '0' && i > index) {
                //剪枝，不能作为前导0，但是他自己是可以单独做为0来使用的
                return false;
            }
            current = current * 10 + c -'0';
            if (count >= 2) {
                long sum = prevprev + prev;
                if (current > sum) {
                    //剪枝，如果当前数比之前两数的和大，则false
                    return false;
                }
                if (current < sum) {
                    //剪枝，如果当前数比之前两数的和小，则继续添加新的字符
                    continue;
                }
            }
            //当前满足条件了，或者还不到两个数，向下一层探索
            if (dfs(num, i + 1, count + 1, prev, current)) {
                return true;
            }
        }
        return false;
    }
}
